package sample.xiaosong.greedyalgorithms;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 寻找最小字典序
 * 贪心算法的经典案例1
 */
public class LowestLexicography {

    public static class LowestComparator implements Comparator<String> {

        @Override
        public int compare(String o1, String o2) {
            return (o1 + o2).compareTo(o2 + o1);
        }
    }

    /**
     * 这个方法的代码很简单，主要是抓住最小字典序的重点。即：
     * 在排列好的字符串队列中，任意挑出两个字符串，交换他们的顺序之后，都会让字符串整体的字典序变大
     * 所以，按照贪心算法的思想，只要保证局部两个字符串字典序是由小到大，就能保证整体字符串的字典序
     * @param strings 字符串数组
     * @return 最小字典序字符串
     */
    public static String getLowestString(String[] strings) {
        if (strings == null || strings.length == 0) {
            return "";
        }
        StringBuilder result = new StringBuilder();
        Arrays.sort(strings, new LowestComparator());
        for (String str : strings) {
            result.append(str);
        }
        return result.toString();
    }

    public static void main(String[] args) {
        String[] strs1 = { "ava", "wff", "cds", "avsw", "abcs" };
        System.out.println(getLowestString(strs1));

        String[] strs2 = { "ca", "cbb" };
        System.out.println(getLowestString(strs2));
    }
}
